package site.wanjiahao.union;

import java.util.Arrays;

/**
 * Quick Union
 * find O(logn)
 * Union O(logn)
 * <p>
 * 基于size的优化可能控制起来不是那么稳定，所以需要基于rank的优化
 * <p>
 * 路径压缩，在find时候，把所有的子节点都变成一层
 */
public class UnionFind_QU_R_PC extends UnionFind_QU_R {


    public UnionFind_QU_R_PC(int capacity) {
        super(capacity);
    }

    // 路径压缩算法
    @Override
    public int find(int v) {
        checkRange(v);
        if (v != parents[v]) {
            parents[v] = find(parents[v]);
        }
        return parents[v];
    }
}
